class Solution {
public:
    int inf = 1000000007;
    pair<int, bool> dp[1000][505];
    int numWays(int steps, int arrLen) {
        return dfs(steps, 0, arrLen);
    }
    int dfs(int k, int pos, int size)
    {
        if (!k && !pos) return 1;
        else if (!k) return 0;
        if (dp[k][pos].second) return dp[k][pos].first;
        int ans = dfs(k - 1, pos, size) % inf;
        if (pos + 1 < size) ans += dfs(k - 1, pos + 1, size);
        ans %= inf;
        if (pos - 1 >= 0) ans += dfs(k - 1, pos - 1, size);
        ans %= inf;
        dp[k][pos].second = 1;
        return dp[k][pos].first = ans;
    }
};